Навигация по странице:
1. Хранение графа
2. Выделение памяти
3. Алгоритм BFS
4. Пример обхода на Cи
5. Пример обхода на C++
6. Задача
Обход в ширину:
Вместо того, чтобы двигаться по определенному пути до конца, BFS предполагает движение вперед по одному соседу за раз. Если мы начали обход в вершине i, то в первую очередь мы посетим всех ее соседей по порядку, далее мы спустимся на один уровень ниже и продолжим алгоритм. Другими словами, сначала мы посетим вершины на уровне 1 от i, потом на уровне 2 от i и так далее до конца. С помощью этого алгоритма можно определить минимальное количество ребер между вершиной i и любой достижимой из i вершины.
Если в графе N вершин и M ребер, то сложность обхода составляет O(N + M).
Навигация по странице:
1. Хранение графа
2. Выделение памяти
3. Алгоритм BFS
4. Пример обхода на Cи
5. Пример обхода на C++
6. Задача
Обход в ширину:
Граф будет храниться в массиве структур. Полностью про хранение графа в программе смотрите в разделе представление графа в программе.
Каждый элемент массива структур хранит информацию об одной из вершин графа, а именно:
1) пути из этой вершины;
2) количество таких путей;
3) посещали ли мы уже эту вершину или нет.
Вот так выглядит такая структура:
struct vertice { int* paths; // пути int number_of_paths; // кол-во путей int flag; // были вершине или нет };
Так как изначально мы не знаем сколько у каждой вершины путей, то придется выделять такую память динамически. В начале программы нужно для каждого элемента массива структур динамически выделить память под один элемент массива путей с помощью функции malloc. Далее после каждого ввода пары вершин, описывающие связь ребром между этими вершинами, мы выделяем дополнительный элемент с помощью функции realloc:
scanf("%i%i", &v, &u); // между этими вершинами есть путь Graph[v - 1].paths = realloc(Graph[v - 1].paths, (Graph[v - 1].number_of_paths + 2) * sizeof(int)); Graph[u - 1].paths = realloc(Graph[u - 1].paths, (Graph[u - 1].number_of_paths + 2) * sizeof(int));
Сразу после этого добавляем в массив путей новую вершину, в которую можно попасть из текущей. Добавление путей для неориентированного графа:
Graph[v - 1].paths[Graph[v - 1].number_of_paths] = u - 1; Graph[v - 1].number_of_paths++; Graph[u - 1].paths[Graph[u - 1].number_of_paths] = v - 1; Graph[u - 1].number_of_paths++;
Таким образом мы добавили путь из v в u и наоборот.
Для ориентированного графа необходимы только первые две строчки при условии, что ребро имеет направление из v в u.
Естественно изначально у каждой вершины количество путей равно нулю и никакую вершину мы еще не посещали, поэтому для любой i верно, что
Graph[i].flag = 0 и Graph[i].number_of_paths = 0.
Для обхода вершин графа используется очередь.
Изначально в очередь добавляем стартовую вершину. Работа с очередью состоит из двух частей:
1. Добавление всех вершин доступных из v, которые мы еще не посещали, v - номер вершины, находящаяся в начале очереди;
2. Удаление вершины v.
Алгоритм завершается, когда в очереди не остается элементов.
В языке Си нет отдельного класса очереди, поэтому создаем его сами и используем для конкретных задач алгоритма. В данном примере проверяется
правильность выделения памяти под динамические массивы.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#define _CRT_SECURE_NO_WARNINGS #include<stdio.h> #include<stdlib.h> #include<malloc.h> #define SIZE 100 struct vertice { int* paths; int number_of_paths; int flag; }; struct queue { struct queue* next; int X; }; struct queue* enqueue(struct queue* q, int a) { struct queue* buf = malloc(sizeof(struct queue)); if (buf) { buf->X = a; buf->next = NULL; q->next = buf; return buf; } return q; } struct queue* dequeue(struct queue* q) { return q->next; } int main() { int n, m, i, v, u, l; struct vertice Graph[SIZE]; scanf("%i%i", &n, &m); for (i = 0; i < SIZE; i++) { // начальная инициализация Graph[i].paths = malloc(sizeof(int)); Graph[i].number_of_paths = Graph[i].flag = 0; } i = 0; while (i < m) { scanf("%i%i", &v, &u); if (v > 0 && v < SIZE && u > 0 && u < SIZE) { int* buf1 = realloc(Graph[v - 1].paths, ((Graph[v - 1].number_of_paths + 2) * sizeof(int))); int* buf2 = realloc(Graph[u - 1].paths, ((Graph[u - 1].number_of_paths + 2) * sizeof(int))); if (buf1 && buf2) { // проверка realloc Graph[v - 1].paths = buf1; Graph[v - 1].paths[Graph[v - 1].number_of_paths] = u - 1; Graph[v - 1].number_of_paths++; Graph[u - 1].paths = buf2; Graph[u - 1].paths[Graph[u - 1].number_of_paths] = v - 1; Graph[u - 1].number_of_paths++; i++; } else printf("error\n"); } else printf("Введите корректные значения\n"); } int start = 0; // с какой переменной начинается обход int cur; // текущая переменная struct queue* front = malloc(sizeof(struct queue)), *end = malloc(sizeof(struct queue)); if (front && end ) { end = front; end = enqueue(end, start); while (front->next != NULL) { // BFS cur = front->next->X; Graph[cur].flag = 1; l = Graph[cur].number_of_paths; front = dequeue(front); for (i = 0; i < l; i++) { // добавляем в очередь пути из вершины cur if (Graph[cur].paths != NULL) { if (Graph[Graph[cur].paths[i]].flag == 0) { // если еще не посещали вершину Graph[Graph[cur].paths[i]].flag = 1; end = enqueue(end, Graph[cur].paths[i]); } } else printf("error\n"); } } } return 0; }
Если отбросить все сложности с динамическим выделением памяти и посмотреть на алгоритм на c++, реализованный с помощью контейнеров vector и queue, то можно убедиться в простоте алгоритма. Так же анализ кода на c++ поможет лучше разобраться с алгоритмом на Си.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<iostream> #include<vector> #include<queue> using namespace std; struct graph { vector<int> paths; // пути int flag; // были в вершине или нет }; int main() { int n, m, i, x, y, j; struct graph A[100]; queue <int> q; cin >> n >> m; for (i = 0; i < n; i++) { // начальная инициализация A[i].flag = 0; } for (i = 0; i < m; i++) { // заполнение массива структур cin >> x >> y; A[x - 1].paths.push_back(y - 1); A[y - 1].paths.push_back(x - 1); } q.push(0); // очередь вершин A[0].flag = 1; // мы сейчас в этой вершин while (!q.empty()) { int v = q.front(); q.pop(); for (j = 0; j < A[v].paths.size(); j++) { if (A[A[v].paths[j]].flag == 0) { q.push(A[v].paths[j]); A[A[v].paths[j]].flag = 1; } } } return 0; }
В городе P есть n домов, пронумерованных от 1 до n. Дома связывают дороги, при этом можно
добраться из любого дома в любой другой. Саша живет в 1 доме, но ему приходится ходить в магазин, который находится в
доме k. Саша хочет добираться до магазина как можно быстрее. Вам нужно вывести минимальное
количество пройденных дорог от его дома до магазина.
Входные данные:
Первая строка содержит целые числа n(2 ≤ n ≤ 10^5), m(1 ≤ m ≤ 10^5), k(2 ≤ k ≤ 10^5),
- количество домов, количества дорог и дом, в котором находится магазин
соответственно.
Следующие m строк содержат два числа, обозначающие, что есть дорога между домами v и u.
Выходные данные:
Вывести минимальное количество дорог, которые должен пройти Саша от своего дома до магазина.
Пример:
Ввод | Вывод |
6 7 6 1 2 2 4 2 3 1 5 5 6 3 4 5 4 |
2 |
Для решения потребуется хранить еще одну переменную в структуре, а именно количество дорог, которые были пройдены от дома 1 до текущего.
Code.C
© Copyright Павел Калашников 2021
обратная связь code.c04@mail.ru